home *** CD-ROM | disk | FTP | other *** search
/ Qoole for Quake / Qoole for Quake (USA) / Qoole for Quake (USA).bin / Tutorial / HTML / QUBE.ZIP / SRC / MERGE.C < prev    next >
Encoding:
C/C++ Source or Header  |  1996-11-05  |  5.5 KB  |  278 lines
  1. /* merge.c */
  2.  
  3. #include "bsp5.h"
  4.  
  5.  
  6. #define CONTINUOUS_EPSILON    0.001
  7.  
  8. /*
  9. ================
  10. CheckColinear
  11.  
  12. ================
  13. */
  14. void CheckColinear (face_t *f)
  15. {
  16.     int            i, j;
  17.     vec3_t        v1, v2;
  18.     
  19.     for (i=0 ; i<f->numpoints ;i++)
  20.     {
  21. /* skip the point if the vector from the previous point is the same */
  22. /* as the vector to the next point */
  23.         j = (i - 1 < 0) ? f->numpoints - 1 : i - 1;
  24.         VectorSubtract (f->pts[i], f->pts[j], v1);
  25.         VectorNormalize (v1);
  26.         
  27.         j = (i + 1 == f->numpoints) ? 0 : i + 1;
  28.         VectorSubtract (f->pts[j], f->pts[i], v2);
  29.         VectorNormalize (v2);
  30.         
  31.         if (VectorCompare (v1, v2))
  32.             Error ("Colinear edge");            
  33.     }
  34.     
  35. }
  36.  
  37.  
  38. /*
  39. =============
  40. TryMerge
  41.  
  42. If two polygons share a common edge and the edges that meet at the
  43. common points are both inside the other polygons, merge them
  44.  
  45. Returns NULL if the faces couldn't be merged, or the new face.
  46. The originals will NOT be freed.
  47. =============
  48. */
  49. face_t *TryMerge (face_t *f1, face_t *f2)
  50. {
  51.     double        *p1, *p2, *p3, *p4, *back;
  52.     face_t        *newf;
  53.     int            i, j, k, l;
  54.     vec3_t        normal, delta, planenormal;
  55.     double        dot;
  56.     plane_t        *plane;
  57.     qboolean        keep1, keep2;
  58.     
  59.     if (f1->numpoints == -1 || f2->numpoints == -1)
  60.         return NULL;
  61.     if (f1->planeside != f2->planeside)
  62.         return NULL;
  63.     if (f1->texturenum != f2->texturenum)
  64.         return NULL;
  65.     if (f1->contents[0] != f2->contents[0])
  66.         return NULL;
  67.     if (f1->contents[1] != f2->contents[1])
  68.         return NULL;
  69.         
  70. /* */
  71. /* find a common edge */
  72. /*     */
  73.     p1 = p2 = NULL;    /* stop compiler warning */
  74.     j = 0;            /*  */
  75.     
  76.     for (i=0 ; i<f1->numpoints ; i++)
  77.     {
  78.         p1 = f1->pts[i];
  79.         p2 = f1->pts[(i+1)%f1->numpoints];
  80.         for (j=0 ; j<f2->numpoints ; j++)
  81.         {
  82.             p3 = f2->pts[j];
  83.             p4 = f2->pts[(j+1)%f2->numpoints];
  84.             for (k=0 ; k<3 ; k++)
  85.             {
  86.                 if (fabs(p1[k] - p4[k]) > EQUAL_EPSILON)
  87.                     break;
  88.                 if (fabs(p2[k] - p3[k]) > EQUAL_EPSILON)
  89.                     break;
  90.             }
  91.             if (k==3)
  92.                 break;
  93.         }
  94.         if (j < f2->numpoints)
  95.             break;
  96.     }
  97.     
  98.     if (i == f1->numpoints)
  99.         return NULL;            /* no matching edges */
  100.  
  101. /* */
  102. /* check slope of connected lines */
  103. /* if the slopes are colinear, the point can be removed */
  104. /* */
  105.     plane = &planes[f1->planenum];
  106.     VectorCopy (plane->normal, planenormal);
  107.     if (f1->planeside)
  108.         VectorSubtract (vec3_origin, planenormal, planenormal);
  109.         
  110.     back = f1->pts[(i+f1->numpoints-1)%f1->numpoints];
  111.     VectorSubtract (p1, back, delta);
  112.     CrossProduct (planenormal, delta, normal);
  113.     VectorNormalize (normal);
  114.     
  115.     back = f2->pts[(j+2)%f2->numpoints];
  116.     VectorSubtract (back, p1, delta);
  117.     dot = DotProduct (delta, normal);
  118.     if (dot > CONTINUOUS_EPSILON)
  119.         return NULL;            /* not a convex polygon */
  120.     keep1 = dot < -CONTINUOUS_EPSILON;
  121.     
  122.     back = f1->pts[(i+2)%f1->numpoints];
  123.     VectorSubtract (back, p2, delta);
  124.     CrossProduct (planenormal, delta, normal);
  125.     VectorNormalize (normal);
  126.  
  127.     back = f2->pts[(j+f2->numpoints-1)%f2->numpoints];
  128.     VectorSubtract (back, p2, delta);
  129.     dot = DotProduct (delta, normal);
  130.     if (dot > CONTINUOUS_EPSILON)
  131.         return NULL;            /* not a convex polygon */
  132.     keep2 = dot < -CONTINUOUS_EPSILON;
  133.  
  134. /* */
  135. /* build the new polygon */
  136. /* */
  137.     if (f1->numpoints + f2->numpoints > MAXEDGES)
  138.     {
  139. /*        Error ("TryMerge: too many edges!"); */
  140.         return NULL;
  141.     }
  142.  
  143.     newf = NewFaceFromFace (f1);
  144.     
  145. /* copy first polygon */
  146.     for (k=(i+1)%f1->numpoints ; k != i ; k=(k+1)%f1->numpoints)
  147.     {
  148.         if (k==(i+1)%f1->numpoints && !keep2)
  149.             continue;
  150.         
  151.         VectorCopy (f1->pts[k], newf->pts[newf->numpoints]);
  152.         newf->numpoints++;
  153.     }
  154.     
  155. /* copy second polygon */
  156.     for (l= (j+1)%f2->numpoints ; l != j ; l=(l+1)%f2->numpoints)
  157.     {
  158.         if (l==(j+1)%f2->numpoints && !keep1)
  159.             continue;
  160.         VectorCopy (f2->pts[l], newf->pts[newf->numpoints]);
  161.         newf->numpoints++;
  162.     }
  163.  
  164.     return newf;
  165. }
  166.  
  167.  
  168. /*
  169. ===============
  170. MergeFaceToList
  171. ===============
  172. */
  173. qboolean    mergedebug;
  174. face_t *MergeFaceToList (face_t *face, face_t *list)
  175. {    
  176.     face_t    *newf, *f;
  177.     
  178.     for (f=list ; f ; f=f->next)
  179.     {
  180. /*CheckColinear (f);         */
  181. if (mergedebug)
  182. {
  183. Draw_ClearWindow ();
  184. Draw_DrawFace (face);
  185. Draw_DrawFace (f);
  186. Draw_SetBlack ();
  187. }
  188.         newf = TryMerge (face, f);
  189.         if (!newf)
  190.             continue;
  191.         FreeFace (face);
  192.         f->numpoints = -1;        /* merged out */
  193.         return MergeFaceToList (newf, list);
  194.     }
  195.     
  196. /* didn't merge, so add at start */
  197.     face->next = list;
  198.     return face;
  199. }
  200.  
  201.  
  202. /*
  203. ===============
  204. FreeMergeListScraps
  205. ===============
  206. */
  207. face_t *FreeMergeListScraps (face_t *merged)
  208. {
  209.     face_t    *head, *next;
  210.     
  211.     head = NULL;
  212.     for ( ; merged ; merged = next)
  213.     {
  214.         next = merged->next;
  215.         if (merged->numpoints == -1)
  216.             FreeFace (merged);
  217.         else
  218.         {
  219.             merged->next = head;
  220.             head = merged;
  221.         }
  222.     }
  223.  
  224.     return head;
  225. }
  226.  
  227.  
  228. /*
  229. ===============
  230. MergePlaneFaces
  231. ===============
  232. */
  233. void MergePlaneFaces (surface_t *plane)
  234. {
  235.     face_t    *f1, *next;
  236.     face_t    *merged;
  237.     
  238.     merged = NULL;
  239.     
  240.     for (f1 = plane->faces ; f1 ; f1 = next)
  241.     {
  242.         next = f1->next;
  243.         merged = MergeFaceToList (f1, merged);
  244.     }
  245.  
  246. /* chain all of the non-empty faces to the plane */
  247.     plane->faces = FreeMergeListScraps (merged);
  248. }
  249.  
  250.  
  251. /*
  252. ============
  253. MergeAll
  254. ============
  255. */
  256. void MergeAll (surface_t *surfhead)
  257. {
  258.     surface_t       *surf;
  259.     int                     mergefaces;
  260.     face_t          *f;
  261.     
  262.     ShowStatusEntry("Merging all surfaces.");
  263.  
  264.     mergefaces = 0; 
  265.     for (surf = surfhead ; surf ; surf=surf->next)
  266.     {
  267.                 MergePlaneFaces (surf);
  268. Draw_ClearWindow ();
  269.         for (f=surf->faces ; f ; f=f->next)
  270.         {
  271. Draw_DrawFace (f);
  272.             mergefaces++;
  273.         }
  274.     }
  275.     
  276.     ShowTempEntry ("%i merge faces.", mergefaces);
  277. }
  278.